// LinkedList.cpp : Defines the entry point for the console application.
//

#include "stdio.h"
#include "stdlib.h"


struct nodeT
{	
	int	value;
	struct nodeT *next;
	struct nodeT *prev;
	struct nodeT *child;
};

struct nodeT *head = NULL;
struct nodeT *tail = NULL;

int data[17] = {5, 33, 17, 2, 1, 6, 25, 6, 2, 7, 8, 9, 12, 5, 7, 21, 3};

//use head to change members of head, not a ptr to head
int createList(nodeT **h, int start, int end)
{
	int i;
	nodeT *p, *q;
	
	if(!(*h)){

		p = (nodeT*)malloc(sizeof(struct nodeT));
		if(!p)
			return 0;

		p->value = data[start];
		p->prev = NULL;
		p->next = NULL;
		p->child = NULL;
				
		*h = p;

		//Read the remaining elements
		for(i = start+1; i<=end; i++){

			q = (nodeT*)malloc(sizeof(struct nodeT));
			if(!q)
				return 0;

			q->value = data[i];
			q->prev = p;
			q->next = NULL;
			q->child = NULL;

			printf("Added a new node at level with head node %d  : %d\n", (*h)->value, q->value);
			
			p->next = q;
			p = q;
		}

		return 1;
	}
	
	return 0;

}

int dfs(nodeT* h, int level)
{
	int i;
	nodeT *p;

	for(p=h; p!=NULL; p = p->next){
		
		for(i=0; i<level; i++, printf(" "));
		
		printf("%d\n", p->value);

		if(p->child != NULL)
			dfs(p->child, level + 1);
	}

	return 1;	
}

int flattenList(nodeT *parent);

int AppendChild(nodeT *h)
{
	nodeT *p, *q;

	h->child->prev = h;

	//q 1 step behind, to ensure p touches all nodes
	for(p=h->child; p != NULL; q = p, p = p->next)
		if(p->child)
			flattenList(p->child);

	q->next = h->next;

	if(h->next)
		h->next->prev = q;	

	h->next = h->child;
	h->child = NULL;

	return 1;

}

int flattenList(nodeT *list)
{
	nodeT *p;

	//q 1 step behind, to ensure p touches all nodes
	for(p=list; p != NULL; tail = p, p = p->next)
		if(p->child)
			AppendChild(p);	

	return 1;

}

int main(int argc, char* argv[])
{
	int i;
	nodeT *p;

	
	
	createList(&head, 0, 4);

	p = head;
	printf("Adding new child list at %d\n", p->value);	
	createList(&p->child, 5, 7);

	for(p=head, i=1; i<=3; i++, p = p->next);

	printf("Adding new child list at %d\n", p->value);	
	createList(&p->child, 8, 9);

	//level 2
	for(p=head->child, i=1; i<=1; i++, p = p->next);
	printf("Adding new child list at %d\n", p->value);	
	createList(&p->child, 10, 10);


	for(p=head->child, i=1; i<=2; i++, p = p->next);
	printf("Adding new child list at %d\n", p->value);	
	createList(&p->child, 11, 11);

	for(p=head, i=1; i<=3; i++, p = p->next);
	printf("Adding new child list at %d\n", p->value);
	printf("Adding new child list at %d\n", p->child->value);	
	createList(&(p->child->child), 12, 13);

	//level 3
	for(p=head->child, i=1; i<=2; i++, p = p->next);
	createList(&(p->child->child), 14, 14);

	for(p=head, i=1; i<=3; i++, p = p->next);
	createList(&(p->child->child->child), 15, 16);


	dfs(head, 0);

	printf("\nFlattening list %d\n", head->value);
	flattenList(head);

	dfs(head, 0);

	
	return 0;
}

